package algorithm.数据量猜解法;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class SnacksWays {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int bag = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        long ways = fun1(arr, bag);
        System.out.println(ways);
        sc.close();
    }

    public static int fun1(int[] v, int w){
        int length = v.length;
        int[][] dp = new int[length][w + 1];
        dp[0][0] = 1;
        if(w >= v[0])
            dp[0][v[0]] = 1;
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < w + 1; j++) {
                int noput = dp[i - 1][j];
                int put = 0;
                if (j - v[i] >= 0 && dp[i - 1][j - v[i]] != 0) {
                    put = dp[i - 1][j - v[i]];
                }
                if (noput != 0 && put != 0) {
                    dp[i][j] = put + noput;
                } else {
                    dp[i][j] = noput != 0 ? noput : put != 0 ? put : 0;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i <= w; i++) {
            sum += dp[length - 1][i];
        }
        return sum;
    }

    public static int fun2(int[] v, int w){
        int length = v.length;
        int mid = (length - 1) / 2;

        TreeMap<Integer, Integer> leftMap = new TreeMap<>();
        TreeMap<Integer, Integer> rightMap = new TreeMap<>();

        int left = process(v, w, 0, mid, 0, leftMap);
        int right = process(v, w, mid + 1, length - 1, 0, rightMap);

        TreeMap<Integer, Integer> sumMap = new TreeMap<>();
        int sum_right = 0;
        for (Map.Entry<Integer, Integer> entry : rightMap.entrySet()) {
            sum_right += entry.getValue();
            sumMap.put(entry.getKey(), sum_right);
        }

        int total = left + right + 1;
        for (Map.Entry<Integer, Integer> entry : leftMap.entrySet()) {
            Map.Entry<Integer, Integer> floorEntry = sumMap.floorEntry(w - entry.getKey());
            if(floorEntry != null){
                Integer right_num = floorEntry.getValue();
                total += entry.getValue() * right_num;
            }
        }

        return total;

    }


    public static int process(int[] v, int w, int index, int end, long sum, TreeMap<Integer, Integer> map){
        if(index == end + 1){
            if(sum > w || sum == 0)
                return 0;
            if(map.containsKey((int)sum))
                map.put((int) sum, map.get((int)sum)  + 1);
            else
                map.put((int) sum, 1);
            return 1;
        }

        int a = process(v, w, index + 1, end, sum,  map);
        int b = process(v, w, index + 1, end, sum + v[index], map);

        return a + b;
    }
}
